GATE CSE 2004
Q11.
Consider the label sequences obtained by the following pairs of traversals on a labeled binary tree. Which of these pairs identify a tree uniquely? (i) preorder and postorder (ii) inorder and postorder (iii) preorder and inorder (iv) level order and postorderQ12.
Consider the following C program segment struct CellNode { struct CelINode *leftchild; int element; struct CelINode *rightChild; } int Dosomething(struct CelINode *ptr) { int value = 0; if (ptr != NULL) { if (ptr->leftChild != NULL) value = 1 + DoSomething(ptr->leftChild); if (ptr->rightChild != NULL) value = max(value, 1 + DoSomething(ptr->rightChild)); } return (value); } The value returned by the function DoSomething when a pointer to the root of a non-empty tree is passed as argument isQ14.
Which of the following grammar rules violate the requirements of an operator grammar? P, Q, R are nonterminals, and r,s,t are terminals. (i)P\rightarrow QR (ii)P\rightarrow QsR (iii)P\rightarrow \varepsilon (iv)P\rightarrow QtRrQ15.
Consider an operating system capable of loading and executing a single sequential user process at a time. The disk head scheduling algorithm used is First Come First Served (FCFS). If FCFS is replaced by Shortest Seek Time First (SSTF), claimed by the vendor to give 50% better benchmark results, what is the expected improvement in the I/O performance of user programs?Q16.
A unix-style I-node has 10 direct pointers and one single, one double and one triple indirect pointers. Disk block size is 1 Kbyte, disk block address is 32 bits, and 48-bit integers are used. What is the maximum possible file size?Q17.
The following is the incomplete operation table of a 4-element group. The last row of the table isQ18.
The elements 32, 15, 20, 30, 12, 25, 16, are inserted one by one in the given order into a MaxHeap. The resultant MaxHeap isQ19.
A circuit outputs a digit in the form of 4 bits. 0 is represented by 0000, 1 by 0001,..., 9 by 1001. A combinational circuit is to be designed which takes these 4 bits as input and outputs 1 if the digit \geq5, and 0 otherwise. If only AND, OR and NOT gates may be used, what is the minimum number of gates required?Q20.
Consider a multiplexer with X and Y as data inputs and Z as control input. Z = 0 selects input X, and Z = 1 selects input Y. What are the connections required to realize the 2-variable Boolean function f=T+R, without using any additional hardware?